Target devices such as field programmable gate arrays (FPGAs), application specific integrated circuits (ASICs), and structured ASICs are used to implement large systems that may include millions of gates and megabits of embedded memory. The complexity of a large system often requires the use of electronic design automation (EDA) tools to create and optimize a design for the system onto physical target devices. Among the procedures performed by EDA tools in a computer aided design (CAD) compilation flow are design generation and integration, synthesis, placement, and routing of the system on the target device.
When addressing conventional timing closure, designers focus on the critical paths in a design. A critical path is a path from a register to another register, through combinational or routing elements, which fails or is close to failing a timing requirement. In an effort to close timing, a designer may examine the critical path and attempt to improve it by reducing an amount of combinational or routing delay along the path.
EDA tools may utilize register retiming algorithms in order to close timing. Register retiming is a synchronous circuit transformation that is used to improve the speed-performance of a synchronous circuit. Register retiming involves moving register across combinational or routing circuit elements in order to reduce the length of timing-critical paths. Register retiming may also involve inserting pipelined registers along timing-critical paths in order to split combinational logic into multiple cycles which leads to an increase of slack in timing-critical paths. This allows for an increase in clock rate, and/or an increase in throughput. The combinational structure remains unchanged and the observable behavior of the circuit is identical to the original circuit.